Crate hibitset

source ·
Expand description

hibitset

Provides hierarchical bit sets, which allow very fast iteration on sparse data structures.

What it does

A BitSet may be considered analogous to a HashSet<u32>. It tracks whether or not certain indices exist within it. Its implementation is very different, however.

At its root, a BitSet relies on an array of bits, which express whether or not indices exist. This provides the functionality to add( ) and remove( ) indices.

This array is referred to as Layer 0. Above it, there is another layer: Layer 1. Layer 1 acts as a ‘summary’ of Layer 0. It contains one bit for each usize bits of Layer 0. If any bit in that usize of Layer 0 is set, the bit in Layer 1 will be set.

There are, in total, four layers. Layers 1 through 3 are each a summary of the layer immediately below them.

Example, with an imaginary 4-bit usize:

Layer 3: 1------------------------------------------------ ...
Layer 2: 1------------------ 1------------------ 0-------- ...
Layer 1: 1--- 0--- 0--- 0--- 1--- 0--- 1--- 0--- 0--- 0--- ...
Layer 0: 0010 0000 0000 0000 0011 0000 1111 0000 0000 0000 ...

This method makes operations that operate over the whole BitSet, such as unions, intersections, and iteration, very fast (because if any bit in any summary layer is zero, an entire range of bits below it can be skipped.)

However, there is a maximum on index size. The top layer (Layer 3) of the BitSet is a single usize long. This makes the maximum index usize**4 (1,048,576 for a 32-bit usize, 16,777,216 for a 64-bit usize). Attempting to add indices larger than that will cause the BitSet to panic.

Structs

  • AtomicBitSet
    This is similar to a BitSet but allows setting of value without unique ownership of the structure
  • BitIter
    An Iterator over a BitSetLike structure.
  • BitParIter
    A ParallelIterator over a BitSetLike structure.
  • BitProducer
    Allows splitting and internally iterating through BitSet.
  • BitSet
    A BitSet is a simple set designed to track which indices are placed into it.
  • BitSetAll
    BitSetAll is a bitset with all bits set. Essentially the same as BitSetNot(BitSet::new()) but without any allocation.
  • BitSetAnd
    BitSetAnd takes two BitSetLike items, and merges the masks returning a new virtual set, which represents an intersection of the two original sets.
  • BitSetNot
    BitSetNot takes a BitSetLike item, and produced an inverted virtual set. Note: the implementation is sub-optimal because layers 1-3 are not active.
  • BitSetOr
    BitSetOr takes two BitSetLike items, and merges the masks returning a new virtual set, which represents an merged of the two original sets.
  • BitSetXor
    BitSetXor takes two BitSetLike items, and merges the masks returning a new virtual set, which represents an merged of the two original sets.
  • DrainBitIter
    A draining Iterator over a DrainableBitSet structure.

Traits